Fidélité du système RSA

Propriété

Soit \(p\) et \(q\) deux nombres premiers distincts. On note \(N=pq\) et \(n=(p-1)(q-1)\) .

Soit \(c\) un entier tel que \(1 \leqslant c et \(\mathrm{PGCD}(c;n)=1\) . Alors

1. il existe un unique entier \(d\) tel que \(1 \leqslant d et \(cd \equiv 1 \ [n]\) ;

2. pour tous \(a\) , \(b \in \mathbb{N}\) , si \(b \equiv a^c \ [N]\) , alors \(a \equiv b^d \ [N]\) ; autrement dit \(a^{cd} \equiv a \ [N]\) .

Remarque

Le second point de la propriété précédente assure qu'à l'étape de décodage du message par le destinataire, il obtient \(b' \equiv a^{cd} \equiv a \ [N]\) .
Ainsi, le destinataire retrouve bien le message original envoyé par l'expéditeur. Cela justifie la fidélité du codage RSA.